package org.example.dataStructure;

import java.io.*;

/**
 * 稀疏数组
 */
public class SparseArray {
    
    /**
     * 原始二维数组 与 稀疏数组 互转
     * @param args
     */
    public static void main(String[] args) {
        // 创建二维数组
        int row = 11;
        int col = 11;
        int[][] chessArr = new int[row][col];
        // 给二维数组赋值，0表示没有棋子，1表示黑子，2表示蓝子
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        chessArr[3][4] = 2;

        System.out.println("原始二维数组：");
        // 遍历原始二维数组
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                System.out.printf("%d\t", chessArr[i][j]);
            }
            System.out.println();
        }

        // 原始二维数组 转 稀疏数组
        int[][] sparseArr = toSparseArr(chessArr);

        System.out.println("转换后的稀疏数组：");
        // 遍历稀疏数组
        for (int[] rows : sparseArr) {
            for(int n : rows) {
                System.out.printf("%d\t", n);
            }
            System.out.println();
        }

        // 稀疏数组保存到磁盘 map.data
        File file = saveToFile(sparseArr);
        // 将 map.data恢复成稀疏数组
        sparseArr = resumeToSparseArr(file);

        // 稀疏数组 转 原始二维数组
        int[][] chessArr2 = to2DArr(sparseArr);

        System.out.println("转换后的原始二维数组：");
        for (int i = 0; i < chessArr2.length; i++) {
            for (int j = 0; j < chessArr2[i].length; j++) {
                System.out.printf("%d\t", chessArr2[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 原始二维数组 转 稀疏数组
     * 二维数组 转 稀疏数组
     * 1.遍历 原始二维数组，得到有效个数的 sum
     * 2.根据 sum 创建 稀疏数组 sparseArr = int[sum+1][3]
     * 3.将二维数组的有数据存入到稀疏数组中
     * @param chessArr 原始二维数组
     * @return 稀疏数组
     */
    public static int[][] toSparseArr(int[][] chessArr) {
        // 遍历 原始二维数组，得到有效个数的 sum
        int sum = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                if (chessArr[i][j] != 0) {
                    sum++;
                }
            }
        }
        System.out.println("有效个数的 sum = " + sum);
        // 根据 sum 创建 稀疏数组 sparseArr = int[sum+1][3]
        // 再读取稀疏数组后面几行，并赋值给 原始二维数组
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = chessArr.length;
        sparseArr[0][1] = chessArr[0].length;
        sparseArr[0][2] = sum;
        
        int index = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                if (chessArr[i][j] != 0) {
                    index++;
                    sparseArr[index][0] = i;
                    sparseArr[index][1] = j;
                    sparseArr[index][2] = chessArr[i][j];
                }
            }
        }
        return sparseArr;
    }

    /**
     * 稀疏数组 转 原始二维数组
     * 稀疏数组 转 二维数组
     * 1.先读取稀疏数组的第一行，根据第一行数据，创建 原始二维数组 chessArr = int[11][11]
     * 2.再读取稀疏数组后面几行，并赋值给 原始二维数组
     * @param sparseArr 稀疏数组
     * @return 原始二维数组
     */
    public static int[][] to2DArr(int[][] sparseArr) {
        // 先读取稀疏数组的第一行，根据第一行数据，创建 原始二维数组 chessArr = int[11][11]
        int[][] chessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
        // 再读取稀疏数组后面几行，并赋值给 原始二维数组
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return chessArr;
    }

    /**
     * 将稀疏数组保存到磁盘
     * @param sparseArr
     * @return
     */
    public static File saveToFile(int[][] sparseArr) {
        String filePath = "D:\\map.data";
        File file = new File(filePath);
        try {
            FileOutputStream fos = new FileOutputStream(file);
            OutputStreamWriter osw = new OutputStreamWriter(fos);

            for (int i = 0; i < sparseArr.length; i++) {
                osw.write(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2] + ",");
            }

            osw.close();
            fos.close();
            System.out.println("稀疏数组已保存在硬盘，路径为：" + filePath);
        } catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return file;
    }

    /**
     * 将磁盘文件恢复成稀疏数组
     * @param mapData
     * @return
     */
    public static int[][] resumeToSparseArr(File mapData) {
        int[][] sparseArr = null;
        try {
            FileInputStream fis = new FileInputStream(mapData);
            InputStreamReader isr = new InputStreamReader(fis);
            StringBuilder sb = new StringBuilder();

            while (isr.ready()) {
                sb.append((char) isr.read());
            }

            isr.close();
            fis.close();

            String[] data = sb.toString().split(",");
            sparseArr = new int[data.length/3][3];
            sparseArr[0][0] = Integer.parseInt(data[0]);
            sparseArr[0][1] = Integer.parseInt(data[1]);
            sparseArr[0][2] = Integer.parseInt(data[2]);

            for (int i = 3; i < data.length; i += 3) {
                int row = Integer.parseInt(data[i]);
                int col = Integer.parseInt(data[i + 1]);
                int val = Integer.parseInt(data[i + 2]);
                sparseArr[i/3][0] = row;
                sparseArr[i/3][1] = col;
                sparseArr[i/3][2] = val;
            }
            System.out.println("map.data已恢复为稀疏数组：");

            for (int[] rows : sparseArr) {
                for(int n : rows) {
                    System.out.printf("%d\t", n);
                }
                System.out.println();
            }

        } catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return sparseArr;
    }
}
